package 算法.leetcode.offer;

/**
 * 约瑟夫环
 *
 * @author lchenglong
 * @date 2022/3/20
 */
public class Offer62_II {

    public static void main(String[] args) {
        Offer62_II instance = new Offer62_II();
        int ans = instance.lastRemaining2(10, 17);
        System.out.println(ans);
    }
    public int lastRemaining(int n, int m) {

        return dfs(n,m);
    }

    public int dfs(int n, int m) {
        if (n == 1) {
            return 0;
        }
        int x = dfs(n - 1, m);
        return (m + x) % n;
    }

    /**
     * 令 x=f(n-1,m)
     * f(n,m)=[(m-1)%n+x+1]%n
     *       =[(m-1)%n%n+(x+1)%n]%n
     *       =[(m-1)%n+(x+1)%n]%n
     *       =(m-1+x+1)%n
     *       =(m+x)%n
     * @param n
     * @param m
     * @return
     */
    public int lastRemaining2(int n, int m) {
        int x = 0;
        for (int i=2;i<n+1;i++){
            x = (m+x)%i;
        }
        return x;
    }

}
